Paint in two colors → Cut graphs